package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1239 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxLength(List<String> arr) {
            List<String> filteredArr = arr.stream().filter(it -> isNoRepeatStr(it)).collect(Collectors.toList());
            return dfs(filteredArr, new int[26], 0);
        }

        public int dfs(List<String> filteredArr, int[] curRes, int curStartIdx) {
            if (curStartIdx >= filteredArr.size()) return 0;
            // 当前位置如果选
            int lenChooseCur = 0;
            if (canAdd(curRes, filteredArr.get(curStartIdx))) {
                addRes(curRes, filteredArr.get(curStartIdx));
                lenChooseCur = dfs(filteredArr, curRes, curStartIdx + 1) + filteredArr.get(curStartIdx).length();
                purgeAdd(curRes, filteredArr.get(curStartIdx));
            }

            int lenNoChooseCur = dfs(filteredArr, curRes, curStartIdx + 1);
            return Math.max(lenChooseCur, lenNoChooseCur);
        }

        public void purgeAdd(int[] curRes, String next) {
            for (char ch : next.toCharArray()) {
                curRes[ch - 'a']--;
            }
        }

        public void addRes(int[] curRes, String next) {
            for (char ch : next.toCharArray()) {
                curRes[ch - 'a']++;
            }
        }


        public boolean canAdd(int[] curRes, String next) {
            int[] curResCopy = Arrays.copyOf(curRes, curRes.length);
            for (char ch : next.toCharArray()) {
                if (curResCopy[ch - 'a'] > 0) return false;
                else curResCopy[ch - 'a']++;
            }

            return true;
        }

        public boolean isNoRepeatStr(String str) {
            int[] visited = new int[26];
            for (char ch : str.toCharArray()) {
                if (visited[ch - 'a'] > 1) return false;
                else visited[ch - 'a']++;
            }

            return true;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        arr = ["un","iq","ue"]
        List<String> arr = Arrays.asList(InputUtil.toStringArray("\"cha\",\"r\",\"act\",\"ers\""));
        System.out.println(solution.maxLength(Arrays.asList("abcdefghijklmnopqrstuvwxyz")));
    }

    public static void main(String[] args) throws Exception {
        LC1239 an = new LC1239();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
